package 力扣.树.前序遍历;

import sun.reflect.generics.tree.Tree;

import java.sql.ClientInfoStatus;
import java.util.ArrayList;
import java.util.List;

public class 路径总和II_113 {
    List<List<Integer>> ans;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
         ans = new ArrayList<>();
         List<Integer> list = new ArrayList<>();
         int sum = 0;
         backTrace(root, list,sum,targetSum);
         return ans;
    }
    private void backTrace(TreeNode root,List<Integer> list,int sum,int target){
        if (root == null){
            return;
        }
        sum += root.val;
        list.add(root.val);
        if (root.left == null && root.right == null){
            if (sum == target){
                ans.add(new ArrayList<>(list));
            }
        }else {
            backTrace(root.left, list, sum, target);
            backTrace(root.right, list, sum, target);
        }
        list.remove(list.size() - 1);
    }




    public List<List<Integer>> pathSum2(TreeNode root, int targetSum) {
          arrs = new ArrayList<>();
          ans2 = new ArrayList<>();
          preDfs(root, targetSum);
          return ans2;
    }
    private int teSum = 0;
    private ArrayList<Integer> arrs = null;
    private ArrayList<List<Integer>> ans2 = null;

    private void preDfs(TreeNode root,int targetSum){
        if (root == null){
            return;
        }
        teSum += root.val;
        arrs.add(root.val);
        if (root.left == null && root.right == null){
            if (teSum == targetSum){
                ans2.add(new ArrayList<>(arrs));
            }
        }else {
            preDfs(root.left, targetSum);
            preDfs(root.right, targetSum);
        }
        //回溯时别忘记还原
        teSum -= root.val;
        arrs.remove(arrs.size() - 1);
    }



    public List<List<Integer>> pathSum3(TreeNode root, int targetSum) {
         list3 = new ArrayList<>();
         ansList3 = new ArrayList<>();
         sum3 = 0;
         preDfs3(root, targetSum);
         return ansList3;
    }
    private ArrayList<Integer> list3;
    private ArrayList<List<Integer>> ansList3;
    private int sum3;
    private void preDfs3(TreeNode root,int targetSum){
        if (root != null){
            sum3 += root.val;
            list3.add(root.val);
            if (root.left == null && root.right == null){
                if (sum3 == targetSum){
                    ansList3.add(new ArrayList<>(list3));
                }
            }else {
                preDfs3(root.left, targetSum);
                preDfs3(root.right, targetSum);
            }
            sum3 -= root.val;
            list3.remove(list3.size() - 1);//回溯
        }
    }

    public List<List<Integer>> pathSum4(TreeNode root, int targetSum) {
           if (root == null){
               return new ArrayList<>();
           }
           ans = new ArrayList<>();
           List<Integer> box = new ArrayList<>();
           int teSum = 0;
           preDfs4(root,teSum,targetSum,box);
           return ans;
    }

    private void preDfs4(TreeNode root, int teSum,int targetSum, List<Integer> box) {
        if (root != null){
            teSum += root.val;
            box.add(root.val);
            if (root.left == null && root.right == null){//到达叶子节点
                if (teSum == targetSum){
                    ans.add(new ArrayList<>(box));
                }
            }else {
                if (root.left != null){
                    preDfs4(root.left, teSum, targetSum, box);
                }
                if (root.right != null){
                    preDfs4(root.right, teSum, targetSum, box);
                }
            }
//            teSum -= root.val;//基本数据类型不需要进行回溯
            box.remove(box.size() - 1);//回溯
        }
    }

}
